package com.zsj.Tree;

import java.util.*;

/**
 * @Author zsj
 * @Version 1.0
 * @Date 2024/4/14 9:48
 * @Description 后缀转表达树
 */
public class TreeToSuffixExpression {

    private class TreeNode {
        String val;
        TreeNode left;
        TreeNode right;


        public TreeNode(String val) {
            this.val = val;
        }

        public TreeNode(String val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    List<String> expressions = Arrays.asList("+", "-", "*", "/");

    /**
     * 后缀表达式转化为表达式树
     * <p>
     * 遇到数字入栈
     * 遇到运算符出栈，构建节点关系，再入栈
     */
    public TreeNode constructExpressionTree(String[] tokens) {
        Stack<TreeNode> stack = new Stack<>();
        for (String token : tokens) {
            if (expressions.contains(token)) {
                TreeNode pop = stack.pop();
                TreeNode pop2 = stack.pop();
                stack.push(new TreeNode(token, pop2, pop));
            } else stack.push(new TreeNode(token));
        }
        return stack.pop();
    }


    public static void main(String[] args) {
        TreeNode treeNode = new TreeToSuffixExpression()
                .constructExpressionTree(new String[]{"2", "1", "-", "3", "*"});

        //再次层序遍历
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.offer(treeNode);
//        while (!queue.isEmpty()) {
//            int size = queue.size();
//            for (int i = 0; i < size; i++) {
//                TreeNode poll = queue.poll();
//                System.out.println(poll.val);
//                if (poll.left != null) queue.offer(poll.left);
//                if (poll.right != null) queue.offer(poll.right);
//            }
//        }

        //后序遍历
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode cur = treeNode;
        TreeNode pop = null;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                //记录来的路
                stack.push(cur);
                cur = cur.left;
            } else {
                //处理右边
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == pop) {
                    pop = stack.pop();
                    System.out.println(pop.val);
                } else cur = peek.right;
            }
        }
    }
}
